package com.zyk.grate_offer.class03;

/**
 * 返回边框全是1的最大正方形面积
 * 题目： https://leetcode-cn.com/problems/largest-1-bordered-square/
 *
 * @author zhangsan
 * @date 2021/4/28 9:33
 */
public class Code03_Largest1BorderedSquare {


    // 暴力 O(N^4)
    public static int largest1BorderedSquare(int[][] grid) {
        int maxLen = 0;
        int height = grid.length;
        int width = grid[0].length;
        for (int i = 0; i < height; i++) {      // 从上往下， 从左往右尝试
            for (int j = 0; j < width; j++) {
                if (grid[i][j] == 1) {
                    int curLen = maxLen;
                    while (i + curLen < height && j + curLen < width) { // 宽高不越界
                        boolean flag1 = true;
                        for (int temp_i = i, temp_j = j; temp_i < i + curLen + 1 && temp_j < j + curLen + 1; temp_i++, temp_j++) {
                            if (grid[i][temp_j] == 0 || grid[temp_i][j] == 0) {
                                flag1 = false;
                                break;
                            }
                        }
                        if (!flag1) break;
                        boolean flag2 = true;
                        for (int temp_i = i + curLen, temp_j = j + curLen, _i = temp_i, _j = temp_j; temp_i > i && temp_j > j; temp_i--, temp_j--) {
                            if (grid[temp_i][_j] == 0 || grid[_i][temp_j] == 0) {
                                curLen++;
                                flag2 = false;
                                break;
                            }
                        }
                        if (!flag2) continue;
                        maxLen = ++curLen;
                    }
                }
            }
        }
        return maxLen * maxLen;
    }

    // 提前整理数组， 使中间的过程是O(1)的， 二位矩阵点正方形 O(N^3), 总时间复杂度O(N^3)
    public static int largest1BorderedSquare2(int[][] grid) {
        int R = grid.length;
        int C = grid[0].length;

        int[][] down = new int[R][C],
                right = new int[R][C];  // 因为从上往下， 从左往右找正方形， 所以只需看右下方。
        prepare(grid, down, right, R, C);

        for (int size = Math.min(R, C); size != 0; size--) {
            if (hasSizeOfBorder(size, right, down)) {
                return size * size;
            }
        }
        return 0;
    }

    private static boolean hasSizeOfBorder(int size, int[][] right, int[][] down) {
        for (int i = 0; i != right.length - size + 1; i++) {
            for (int j = 0; j != right[0].length - size + 1; j++) {
                if (right[i][j] >= size && down[i][j] >= size && right[i + size - 1][j] >= size
                        && down[i][j + size - 1] >= size) {
                    return true;
                }
            }
        }
        return false;
    }


    // O(N^2)
    public static void prepare(int[][] grid, int[][] down, int[][] right, int R, int C) {
        // 下数组， 最后一行
        for (int c = 0; c < C; c++) {
            down[R - 1][c] = grid[R - 1][c] == 0 ? 0 : 1;
        }
        // 右数组， 最后一列
        for (int r = 0; r < R; r++) {
            right[r][C - 1] = grid[r][C - 1] == 0 ? 0 : 1;
        }

        // 下数组  从右往左（外层）， 从下往上
        for (int c = C - 1; c >= 0; c--) {
            for (int r = R - 2; r >= 0; r--) {
                down[r][c] = grid[r][c] == 0 ? 0 : down[r + 1][c] + 1;
            }
        }

        // 右数组， 从下往上（外层）， 从右往左（内层）
        for (int r = R - 1; r >= 0; r--) {
            for (int c = C - 2; c >= 0; c--) {
                right[r][c] = grid[r][c] == 0 ? 0 : right[r][c + 1] + 1;
            }
        }

    }

    public static void main(String[] args) {
//        int[][] grid = {
//                {1, 1, 1, 1, 1},
//                {1, 0, 1, 0, 1},
//                {1, 1, 1, 0, 1},
//                {1, 1, 0, 1, 1},
//                {1, 1, 1, 1, 1},
//        };
        int[][] grid = {
                {1, 1},
                {1, 0}
        };
        System.out.println(largest1BorderedSquare(grid));
        System.out.println(largest1BorderedSquare2(grid));
    }

}
